package second.mstack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

public class Solution03 {
    public int[] nextGreaterElements(int[] nums) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.add(0);
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        for (int i = 1; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.getLast()]) {
                res[stack.getLast()] = nums[i];
                stack.removeLast();
            }
            stack.add(i);
        }
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > nums[stack.getLast()]) {
                res[stack.getLast()] = nums[i];
                stack.removeLast();
            }
        }
        return res;
    }
}
